/* MIT License
 *
 * Copyright (c) 2012 Reuben Smith, Miami University
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package org.droidlike.vsig;


import com.jme3.asset.AssetManager;
import com.jme3.material.Material;
import com.jme3.math.ColorRGBA;
import com.jme3.math.Vector3f;
import com.jme3.scene.Geometry;
import com.jme3.scene.Mesh;
import com.jme3.scene.VertexBuffer.Type;
import com.jme3.util.BufferUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;


/**
 * RoadGraph.
 * 
 * @author smithre5
 */
public class RoadGraph
{
    /**
     * Creates a graph from the given nodes with the given edges.
     * 
     * @param nodes the nodes to be added
     * @param edges the edges to be added
     * @return a graph if successful; null otherwise
     */
    public static RoadGraph create(RoadNode[] nodes, int[][] edges)
    {        
        if (nodes == null || edges == null || nodes.length < 2 || edges.length < 1) {
            return null;
        }
        
        RoadGraph graph = new RoadGraph();
        
        for (int i = nodes.length; --i >= 0;) {
            graph.addNode(nodes[i]);
        }
        
        for (int i = edges.length; --i >= 0;) {
            if (edges[i] == null || edges[i].length < 2) {
                continue;
            }
            
            RoadNode[] linkedNodes = new RoadNode[edges[i].length];
            
            for (int j = edges[i].length; --j >= 0;) {
                if (!Util.inRange(edges[i][j], 0, nodes.length - 1)) {
                    continue;
                }
                
                linkedNodes[j] = nodes[edges[i][j]];
            }
            
            graph.linkNodes(linkedNodes);
        }
        
        return graph;
    }
    
    
    /**
     * Creates a mesh from the given graph.
     * 
     * @param graph the graph to be modeled
     * @param assetManager the AssetManager to use
     * @return a Geometry of the graph if successful; null otherwise
     */
    public static Geometry createGeometry(RoadGraph graph, AssetManager assetManager)
    {
        if (graph == null || assetManager == null) {
            return null;
        }
        
        Geometry roadsGeom = new Geometry("roads");
        
        // TODO Generate a proper mesh for the road.
        
        Vector3f[] roadVerts = new Vector3f[graph.getOrder()];
        int[] roadIndices = new int[4 * graph.getSize()];
        
        {
            int i = 0;
            for (Vector3f nodePos : graph.nodes.keySet()) {
                roadVerts[i++] = nodePos.clone();
            }
        }
        
        {            
            int i = 0;
            for (int j = roadVerts.length; --j >= 0;) {
                HashSet<Vector3f> edgeVerts = graph.edges.get(roadVerts[j]);
                if (edgeVerts == null || edgeVerts.isEmpty()) {
                    continue;
                }
               
                for (Vector3f vert : edgeVerts) {
                    roadIndices[i++] = j;
                    roadIndices[i++] = Arrays.asList(roadVerts).indexOf(vert);
                }
            }
        }
        
        // smithre5: Temporary fix to minimize z-fighting.
        for (Vector3f vert : roadVerts) {
            vert.addLocal(0, 2.5f, 0);
        }
        
        Mesh roadsMesh = new Mesh();
        roadsMesh.setMode(Mesh.Mode.Lines);
        roadsMesh.setLineWidth(5.0f);
        roadsMesh.setBuffer(Type.Position, 3, BufferUtils.createFloatBuffer(roadVerts));
        roadsMesh.setBuffer(Type.Index, 2, BufferUtils.createIntBuffer(roadIndices));
        roadsMesh.updateBound();
        roadsMesh.setStatic();
        
        Material roadsMaterial = new Material(assetManager,
            "Common/MatDefs/Misc/Unshaded.j3md");
        roadsMaterial.setColor("Color", ColorRGBA.DarkGray);
        
        // TODO Generate a texture for the road.
        
        roadsGeom.setMaterial(roadsMaterial);
        roadsGeom.setMesh(roadsMesh);
        
        return roadsGeom;
    }
    
    
    /**
     * Default constructor.
     */
    public RoadGraph()
    {
        nodes = new HashMap<Vector3f, RoadNode>();
        edges = new HashMap<Vector3f, HashSet<Vector3f>>();
    }
    
    
    /**
     * Adds a node to the graph.
     * 
     * @param node the node to be added
     */
    public void addNode(RoadNode node)
    {
        if (node == null) {
            return;
        }
        
        nodes.put(node.getPosition(), node);
        ++graphOrder;
    }
    
    
    public Vector3f[] getEdges(Vector3f position)
    {
        if (position == null) {
            return null;
        }
        
        return edges.get(position).toArray(new Vector3f[edges.get(position).size()]);
    }
    
    
    /**
     * Gets all nodes that have only one edge.
     * 
     * @return an array of nodes with only one edge
     */
    public Vector3f[] getLeafPositions()
    {
        ArrayList<Vector3f> leafNodes = new ArrayList<Vector3f>();
        
        for (Entry<Vector3f, HashSet<Vector3f>> entry : edges.entrySet()) {
            if (entry.getValue().size() != 1) {
                continue;
            }
            
            leafNodes.add(entry.getKey());
        }
        
        return leafNodes.toArray(new Vector3f[leafNodes.size()]);
    }
    
    
    /**
     * Returns the node nearest to the given position.
     * 
     * @param position the position to check against
     * @param distanceLimit ignore nodes farther away than this
     * @return the nearest node or null
     */
    public RoadNode getNearestTo(Vector3f position, float distanceLimit)
    {
        // smithre5: This is a very naive approach. kd-tree would make this a
        // lot more effective.
        
        if (position == null) {
            return null;
        }
        
        if (distanceLimit > 0) {
            distanceLimit *= distanceLimit;
        }
        else {
            distanceLimit = Float.POSITIVE_INFINITY;
        }
        
        RoadNode bestNode = null;
        float bestDistSq = Float.MAX_VALUE;
        
        for (Vector3f nodePos : nodes.keySet()) {
            float distSq = nodePos.distanceSquared(position);
            
            if (distSq > distanceLimit) {
                continue;
            }
            
            if (distSq < bestDistSq) {
                bestNode = nodes.get(nodePos);
                bestDistSq = distSq;
            }
        }
        
        return bestNode;
    }
    
    
    /**
     * @param position the position to query
     * @return the RoadNode at the given position; null if none exists
     */
    public RoadNode getNode(Vector3f position)
    {
        return nodes.get(position);
    }
    
    
    /**
     * Returns the number of nodes (the order) in the graph.
     * 
     * @return the number of nodes
     */
    public int getOrder()
    {
        return graphOrder;
    }
    
    
    /**
     * Returns the number of edges (the size) in the graph. This is actually
     * the number of bidirectional edges in the graph. The proper number of
     * edges would be twice this.
     * 
     * @return the number of edges
     */
    public int getSize()
    {
        return graphSize;
    }
    
    
    /**
     * Creates edges between all given nodes. This creates a mesh type linkage.
     * That is, every legal direction of travel is possible. Real road systems
     * might disallow turning one way or another. 
     * 
     * @param nodes the nodes to be linked
     */
    public void linkNodes(RoadNode... nodes)
    {        
        if (nodes.length == 0) {
            return;
        }
        
        for (int i = nodes.length; --i > 0;) {
            if (nodes[i] == null) {
                continue;
            }
            
            Vector3f iPos = nodes[i].getPosition();
            HashSet<Vector3f> iEdges = edges.get(iPos);
            
            if (iEdges == null) {
                edges.put(iPos, new HashSet<Vector3f>(3));
                iEdges = edges.get(iPos);
            }
            
            for (int j = i; --j >= 0;) {
                if (nodes[j] == null) {
                    continue;
                }
                
                Vector3f jPos = nodes[j].getPosition();
                HashSet<Vector3f> jEdges = edges.get(jPos);
                
                if (jEdges == null) {
                    edges.put(jPos, new HashSet<Vector3f>(3));
                    jEdges = edges.get(jPos);
                }
                
                if (iEdges.add(jPos) && jEdges.add(iPos)) {
                    if (nodes[i].getDirection().equals(Vector3f.ZERO)) {
                        nodes[i].setDirection(jPos.subtract(iPos));
                    }
                    
                    if (nodes[j].getDirection().equals(Vector3f.ZERO)) {
                        nodes[j].setDirection(iPos.subtract(jPos));
                    }
                    
                    ++graphSize;
                }
            }
        }
    }
        
    
    // smithre5: Is this really ideal? A kd-tree would be useful for picking the
    // node nearest to a point...
    
    // smithre5: This also pays no attention to lane linkage. Traveling from a 
    // node with N lanes to a node with N-1 lanes does... what?
    
    private HashMap<Vector3f, RoadNode> nodes;
    private HashMap<Vector3f, HashSet<Vector3f>> edges;
    
    private int graphOrder;
    private int graphSize;
}

